#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char data;
    struct TreeNode *lchild;
    struct TreeNode *rchild;
    int ltag;
    int rtag;
} TreeNode;

void creatTree(TreeNode **T, char *data, int *index) 
{
    char ch = data[(*index)++];
    if ('#' == ch) {
        *T = NULL;
    } else {
        (*T) = (TreeNode *)malloc(sizeof(TreeNode));
        (*T)->data = ch;
        
        (*T)->ltag = 0;
        (*T)->rtag = 0;
        creatTree(&((*T)->lchild), data, index);
        creatTree(&((*T)->rchild), data, index);
    }
}

void inThreadTree(TreeNode *T, TreeNode **pre) //二级指针全局
{
    if (T) {
        inThreadTree(T->lchild, pre);
        //do something
        if (T->lchild == NULL) {
            T->lchild = *pre;
            T->ltag = 1;
        }
        if (*pre != NULL && (*pre)->rchild == NULL) {
            (*pre)->rchild = T;
            (*pre)->rtag = 1;
        }
        (*pre) = T;
        inThreadTree(T->rchild, pre);
    }
}

TreeNode *getFirst(TreeNode *T) //前驱ltag = 1;
{
    while (T->ltag == 0) 
        T = T->lchild;
    return T;
}

TreeNode *getNext(TreeNode *node)
{
    if (node->rtag == 1) {
        return node->rchild;
    } else { //左root后面是右子树
        return getFirst(node->rchild);
    }
}

void inOrder (TreeNode *T) 
{
    if (!T) return ;
    inOrder(T->lchild);
    printf("%c ", T->data);
    inOrder(T->rchild);
}

int main(void)
{
    int index = 0;
    char *data = "AB#DF###CEG##H###";
    TreeNode *T;
    TreeNode *pre = NULL;
    creatTree(&T, data, &index);
    inOrder(T);
    inThreadTree(T, &pre);
    (pre)->rchild = NULL;//最后到了 右边的最后一个节点
    (pre)->rtag = 1;
    printf("\n");
    for (TreeNode *node = getFirst(T); node != NULL; node = getNext(node)) {
        printf("%c ", node->data);
    }    

    return 0;
}